/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 62536
 * Date: 2024-02-21
 * Time: 12:15
 */
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }

    //判断链表是否有环
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast) {
                return true;
            }
        }
        return false;
    }

    //求链表的环的入口点
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                ListNode p1 = fast;
                ListNode p2 = head;
                while(p1 != null && p2 != null) {
                    if(p1 == p2){
                        return p1;
                    }
                    p1 = p1.next;
                    p2 = p2.next;

                }
            }
        }

        return null;
    }

    //判断两个链表是否相交
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0;
        int lenB = 0;
        ListNode curA = headA;
        ListNode curB = headB;

        while(headA != null) {
            headA = headA.next;
            lenA++;
        }
        while(headB != null) {
            headB = headB.next;
            lenB++;
        }
        if(lenA > lenB) {
            for(int i = 0; i < lenA-lenB; i++) {
                curA = curA.next;
            }
        } else {
            for(int i = 0; i < lenB-lenA; i++) {
                curB = curB.next;
            }
        }

        while(curA != null) {
            if(curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;


    }

    //链表的回文结构 1 -> 2 -> 3 -> 2 -> 1
    //对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
    public boolean chkPalindrome(ListNode A) {
        //1.找到中间节点
        ListNode fast = A;
        ListNode slow = A;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //2.翻转
        ListNode cur = slow.next;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

        //3.一个往前，一个往后
        while(slow != A) {
            if(slow.val != A.val) {
                return false;
            }
            if(A.next == slow) {
                return true;   //偶数情况
            }
            A = A.next;
            slow = slow.next;
        }

        return true;

    }


    //链表分割
    //现有一链表的头指针 ListNode* pHead，
    // 给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
    public ListNode partition(ListNode pHead, int x) {
        if(pHead == null){
            return null;
        }

        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = pHead;
        while(cur != null) {
            if(cur.val < x) {
                if(bs == null) {
                    bs = cur;
                    be = cur;
                } else {
                    be.next = cur;
                    be = cur;
                }

            } else {
                if(as == null) {
                    as = cur;
                    ae = cur;
                } else {
                    ae.next = cur;
                    ae = cur;
                }
            }
            cur = cur.next;
        }
        if(bs== null){
            return as;
        }
        be.next = as;
        if(as != null){
            ae.next = null; //将结尾的next手动置空，因为结尾可能不是之前的结尾，的next可能不是空
        }

        return bs;


    }
}
